package com.adee.algorithm.graph;

import java.util.LinkedList;

class Graph2 {
    public static final int vCount = 5;
    public int[][] matrix = new int[vCount][vCount];

    public void build() {
        // 参考 Test003_graph_BFS.jpg 中无向图构造邻接矩阵
        // 行表示起始顶点，列表示指向顶点
        matrix[0][1] = 1;
        matrix[0][2] = 1;
        matrix[1][3] = 1;
        matrix[2][3] = 1;
        matrix[3][4] = 1;

        matrix[1][0] = 1;
        matrix[2][0] = 1;
        matrix[3][1] = 1;
        matrix[3][2] = 1;
        matrix[4][3] = 1;



        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {

            }
        }
    }

    public void BFS() {
        // 起始顶点 [0][0]

        // 记录顶点是否被访问过
        boolean[] visited = new boolean[vCount];

        // 使用队列实现BFS算法
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(0); // 起点入队
        // ！！！注意，要在添加的时候访问
        visit(0); // 访问该顶点
        visited[0] = true;  // 标记该顶点被访问过

        while (queue.size() > 0) {
            Integer v = queue.removeFirst(); // 出队一个顶点

            // 将邻居顶点入队
            // 以该顶点为起点 ！！！ 注意，不区分起点或被指向点
            for (int i = 0; i < vCount; i++) {
                if (matrix[v][i] == 1 && !visited[i]) {  // 如果为该顶点的邻居顶点，且该邻居顶点没被访问过，则入队
                    queue.addLast(i);
                    // ！！！注意，要在添加的时候访问
                    visit(i);
                    visited[i] = true;
                }
            }

//            // 同理，以该顶点为被指向顶点 ！！！ 注意，这里不能再添加了，只添加一次邻居节点即可，不用区分该顶点为起点或被指向顶点，否则就会添加两次
//            for (int i = 0; i < vCount; i++) {
//                if (matrix[i][v] == 1 && !visited[i]) {  // 如果为该顶点的邻居节点，且该邻居顶点没被访问过，则入队
//                    queue.addLast(i);
//                }
//            }


        }

    }

    public void visit(Integer v) {
        System.out.println("[" + v+ "]");
    }
}

public class Test003_0_graph_BFS {
    public static void main(String[] args) {
//        testQueue();
        Graph2 g = new Graph2();
        g.build();
        g.BFS();
    }

    public static void testQueue() {
        // 测试使用LinkedList作为队列
        LinkedList<Integer> q = new LinkedList<>();
        q.addLast(1);
        q.addLast(2);
        q.addLast(3);
        System.out.println("q.size()=" + q.size());

        System.out.println(q.removeFirst());
        System.out.println(q.removeFirst());
        System.out.println(q.removeFirst());

        System.out.println("q.size()=" + q.size());
    }
}
